package com.collection;

import java.io.Serializable;
import java.util.Collection;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * Created by houjinxin on 16/4/26.
 */
public class HashMap<K, V> implements Map<K, V>, Cloneable, Serializable {

    static class Node<K, V> implements Map.Entry<K, V> {
        //为什么要final
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        /**
         * 比较的是映射关系是否等价,而不仅是entry对象的引用是否相同
         *
         * @param obj
         * @return
         */
        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            } else if (obj instanceof Map.Entry) {
                Map.Entry e = (Node) obj;
                return Objects.equals(e.getKey(), key) && Objects.equals(e.getValue(), value);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        @Override
        public String toString() {
            return key + "=" + value;
        }
    }

    public final int defaultSize = 16;
    public int size;

    //第一次使用时初始化
    public Node<K, V>[] table = (Node<K, V>[]) new Node[defaultSize];

    public HashMap() {
        this.table = (Node<K, V>[]) new Node[defaultSize];
    }

    public HashMap(int size) {
        this.table = (Node<K, V>[]) new Node[size];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        return false;
    }

    @Override
    public boolean containsValue(Object value) {
        return false;
    }

    @Override
    public V get(Object key) {
        Node<K, V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    private int hash(Object key) {
        int h;
        return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 根据Node的Key的哈希值来取值,不考虑TreeNode
     *
     * @param key
     * @return
     */
    private Node<K, V> getNode(int hash, Object key) {
        Node<K, V>[] tab = null;
        Node<K, V> first = null, e = null;
        int n = 0;
//        int index = hash / size;
        //table不为空且长度大于0,链表的第一元素不为空
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            //先判断链表的第一个元素,若第一个元素是目标节点直接返回 ???为什么总是判断第一个节点
            if (first.hash == hash && (first.key == key || (key != null && key.equals(first.key)))) {
                return first;
            }
            if ((e = first.next) != null) {
                do {
                    if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                        return e;
                    }
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    @Override
    public V put(K key, V value) {
        return putVal(hash(key), key, value);
    }

    private V putVal(int hash, K key, V value) {
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;
        tab = table;
        n = tab.length;
        //链表第一个元素为空,那么将新节点插入第一个元素的位置
        if ((p = tab[i = (n - 1) & hash]) == null) {
            tab[i] = new Node<K, V>(hash, key, value, null);
        } else { //链表不空
            Node<K, V> e = null; //定义要操作(添加next节点或者修改节点value)的节点
            if (p.hash == hash && (p.key == key || (key != null && key.equals(p.key)))) {
                e = p;
            } else {
                /**
                 * 遍历整个链表,只会有两种可能,第一种找到一个节点与匹配key值,拿出来对其进行修改,
                 * 第二种遍历整个链表都找不到一个与key值匹配的节点,那么就在链表的最后加上新的节点
                 */
                while (true) {
                    //不匹配则继续查看后续节点直到找到一个匹配key的节点或者链表的最后一位
                    if ((e = p.next) == null) {
                        p.next = new Node<K, V>(hash, key, value, null);
                        break;
                    }
                    //若当前节点的key匹配key值,则直接跳出循环,在后续步骤修改e
                    if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                        break;
                    }
                    p = e; //每一次的遍历条件是p.next p指向e只是将操作对象置为当前对象的下一个对象
                }
            }
            if (e != null) { //已经存在的Entry,返回旧值设置新值
                return e.setValue(value);
            }
        }
        System.out.println("链表索引为:" + i);
        ++size;
        return null;
    }

    @Override
    public V remove(Object key) {
        Node<K, V> node = null;
        Node<K, V>[] tab;
        Node<K, V> p, e;
        int n;
        tab = table;
        n = tab.length;
        int hash = hash(key);
        int index;
        p = tab[index = (n - 1) & hash]; //p是一个临时节点,可以指代链表第一个元素,也可以表示链表中的节点
        //先判断链表的第一个元素,若第一个元素是目标节点直接返回 ???为什么总是判断第一个节点
        if (p.hash == hash && (p.key == key || (key != null && key.equals(p.key)))) {
            node = p;
        } else if ((e = p.next) != null) {
            do {
                if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                    node = e;
                    break;
                }
                p = e; //若上面的条件不成立,P指向下一个元素
            } while ((e = e.next) != null);
        }
        if (node == p) { //移除第一个元素
            tab[index] = node.next;
        } else { //这时p是node的上一个节点
            p.next = node.next;
        }
        --size;
        return node.getValue();
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {

    }

    @Override
    public void clear() {

    }

    @Override
    public Set<K> keySet() {
        return null;
    }

    @Override
    public Collection<V> values() {
        return null;
    }



    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }

    /**
     * TODO:toString要输出有效entry的键值,所以要对entrySet进行遍历,而不是Node数组
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (Node<K, V> node : table) {
            sb.append(node + ", ");
        }
        return sb.substring(0, sb.length()-1) + "}";
    }

    public static void main(String[] args) {
        Map<Object, Object> map = new HashMap();
        map.put(null, "null");
        map.put(null, "null");
        map.put(new KeyObject(), "keyObj1");
        map.put(new KeyObject(), "keyObj2");
        map.put(new KeyObject(), "keyObj3");
        map.put("a", "a");
        map.put("b", "a");
        map.put("c", "a");
        map.put("d", "a");
        map.entrySet();
//        System.out.println(map.table[0]);
        System.out.println(map.get("a"));
        System.out.println(map.remove(new KeyObject()));
//        System.out.println(map.remove("d"));
    }
}
